5.13 How do I input a newline character in isearch or query-replace?

Use C-q C-j. For more information, see see Special Input for Incremental Search.